package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/10 17:37
 * 链表内指定区间反转
 * 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
 * 算法：链表
 */
public class CC57 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // write code here
        if (head == null) return null;
        ListNode ans = new ListNode(-1), cur = ans, pre = null, begin = null;
        ans.next = head;
        int cnt = 0;
        while (begin == null && cur != null) {
            if (cnt == m - 1) pre = cur;
            if (cnt == m) begin = cur;
            cur = cur.next;
            ++cnt;
        }
        pre.next = reverse(begin, n - m + 1);
        return ans.next;
    }

    ListNode reverse(ListNode begin, int n) {
        ListNode pre = null, cur = begin, next = null;
        while (n-- > 0) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        begin.next = cur;
        return pre;
    }

}
